package datastructure.tree.bst2;


/**
 * 二叉搜索树-查询
 *
 * @author 杨 强
 * @package datastructure.tree.bst2
 * @createTime 2023-03-21 21:50
 */
public class BST01Get {
    public static void main(String[] args) {
        /*
                        3
                       / \
                      2   4
                     /
                    1
         */
        TreeNode node1 = new TreeNode(1, "1", null, null);
        TreeNode node2 = new TreeNode(2, "1", node1, null);
        TreeNode node4 = new TreeNode(4, "1", null, null);
        TreeNode node3 = new TreeNode(3, "1", node2, node4);
        BST01Get bst01 = new BST01Get(node3);
        System.out.println("预计1,实际:" + bst01.get1(1));
        System.out.println("预计1,实际:" + bst01.get2(1));
    }

    /**
     * 二叉搜索树的根节点
     */
    TreeNode root;

    public BST01Get(TreeNode root) {
        this.root = root;
    }

    /**
     * 查找元素-递归
     * @param key 元素的key
     * @return key对应的元素值
     */
    public Object get1(int key){
        return getByRecursion(root, key);
    }

    /**
     * 查找元素的递归函数
     * @param node
     * @param key
     * @return
     */
    public Object getByRecursion(TreeNode node, int key){
        // 为null就退出
        if (node == null){
            return null;
        }
        if (node.key > key){
            return getByRecursion(node.left, key);// 往左找
        }else if (node.key < key){
            return getByRecursion(node.right, key); // 往右找
        }else {
            return node.value; // 找打
        }
    }

    /**
     * 查找元素-while版
     * @param key 元素的key
     * @return key对应的元素值
     */
    public Object get2(int key){
        TreeNode node = root;
        while (node != null){
            if (node.key > key){
                node = node.left;// 往左找
            }else if (node.key < key){
                node = node.right; // 往右找
            }else {
                return node.value; // 找打
            }
        }
        return null;
    }
}
